package com.yanceysong.codetop.s71_s80;

public class S76_Mid_240_搜索二维矩阵_II {
    /**
     * .S76_Mid_240_搜索二维矩阵 II
     * .<p>
     * .<a href="https://leetcode.cn/problems/search-a-2d-matrix-ii/">...</a>
     * .<p>
     * .编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     * .<p>
     * .每行的元素从左到右升序排列。
     * .每列的元素从上到下升序排列。
     * .<p>
     * .示例 1：
     * .输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
     * .输出：true
     * .<p>
     * .示例 2：
     * .输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
     * .输出：false
     * .<p>
     * .提示：
     * .<p>
     * .m == matrix.length
     * .n == matrix[i].length
     * .1 <= n, m <= 300
     * .-10^9 <= matrix[i][j] <= 10^9
     * .每行的所有元素从左到右升序排列
     * .每列的所有元素从上到下升序排列
     * .-10^9 <= target <= 10^9
     * .<p>
     * .核心标签：数组、二分查找、分治、矩阵
     * .<p>
     * .========================================
     * .算法原理：Z字形查找（从右上角或左下角开始）
     * .========================================
     * .<p>
     * .关键洞察：
     * .1. 右上角元素的特殊性质：
     * .   - 它是当前行的最大值（向左递减）
     * .   - 它是当前列的最小值（向下递增）
     * .   - 这使得每次比较都能明确排除一行或一列
     * .<p>
     * .2. 二叉搜索树类比（逆时针旋转45度）：
     * .   将矩阵逆时针旋转45度后，可以类比为二叉搜索树：
     * .   - 右上角元素视为"根节点"
     * .   - 向左移动相当于访问"左子树"（值更小）
     * .   - 向下移动相当于访问"右子树"（值更大）
     * .<p>
     * .算法步骤：
     * .1. 从矩阵的右上角开始（也可以从左下角开始，原理相同）
     * .2. 将当前元素与目标值比较：
     * .   - 如果相等，找到目标，返回true
     * .   - 如果当前元素大于目标，说明目标在当前列的左边，向左移动（col--）
     * .   - 如果当前元素小于目标，说明目标在当前行的下方，向下移动（row++）
     * .3. 重复步骤2，直到找到目标或越界
     * .<p>
     * .为什么从右上角或左下角开始？
     * .- 右上角：向左递减，向下递增（两个方向单调性相反）
     * .- 左下角：向右递增，向上递减（两个方向单调性相反）
     * .- 左上角/右下角：两个方向单调性相同，无法确定搜索方向
     * .<p>
     * .========================================
     * .ASCII 图解：查找 target = 5
     * .========================================
     * .<p>
     * .初始矩阵：
     * .    0   1   2   3   4
     * .  +---+---+---+---+---+
     * .0 | 1 | 4 | 7 | 11| 15|  ← 起始位置：右上角 matrix[0][4] = 15
     * .  +---+---+---+---+---+
     * .1 | 2 | 5 | 8 | 12| 19|
     * .  +---+---+---+---+---+
     * .2 | 3 | 6 | 9 | 16| 22|
     * .  +---+---+---+---+---+
     * .3 | 10| 13| 14| 17| 24|
     * .  +---+---+---+---+---+
     * .4 | 18| 21| 23| 26| 30|
     * .  +---+---+---+---+---+
     * .<p>
     * .查找过程（从右上角开始）：
     * .<p>
     * .步骤1：当前位置 [0,4]，值=15，target=5
     * .    15 > 5，向左移动（排除第4列）
     * .    0   1   2   3
     * .  +---+---+---+---+
     * .0 | 1 | 4 | 7 | 11| ← 当前位置移到 [0,3]
     * .  +---+---+---+---+
     * .1 | 2 | 5 | 8 | 12|
     * .  +---+---+---+---+
     * .2 | 3 | 6 | 9 | 16|
     * .  +---+---+---+---+
     * .3 | 10| 13| 14| 17|
     * .  +---+---+---+---+
     * .4 | 18| 21| 23| 26|
     * .  +---+---+---+---+
     * .<p>
     * .步骤2：当前位置 [0,3]，值=11，target=5
     * .    11 > 5，向左移动（排除第3列）
     * .    0   1   2
     * .  +---+---+---+
     * .0 | 1 | 4 | 7 | ← 当前位置移到 [0,2]
     * .  +---+---+---+
     * .1 | 2 | 5 | 8 |
     * .  +---+---+---+
     * .2 | 3 | 6 | 9 |
     * .  +---+---+---+
     * .3 | 10| 13| 14|
     * .  +---+---+---+
     * .4 | 18| 21| 23|
     * .  +---+---+---+
     * .<p>
     * .步骤3：当前位置 [0,2]，值=7，target=5
     * .    7 > 5，向左移动（排除第2列）
     * .    0   1
     * .  +---+---+
     * .0 | 1 | 4 | ← 当前位置移到 [0,1]
     * .  +---+---+
     * .1 | 2 | 5 |
     * .  +---+---+
     * .2 | 3 | 6 |
     * .  +---+---+
     * .3 | 10| 13|
     * .  +---+---+
     * .4 | 18| 21|
     * .  +---+---+
     * .<p>
     * .步骤4：当前位置 [0,1]，值=4，target=5
     * .    4 < 5，向下移动（排除第0行）
     * .    0   1
     * .  +---+---+
     * .1 | 2 | 5 | ← 当前位置移到 [1,1]
     * .  +---+---+
     * .2 | 3 | 6 |
     * .  +---+---+
     * .3 | 10| 13|
     * .  +---+---+
     * .4 | 18| 21|
     * .  +---+---+
     * .<p>
     * .步骤5：当前位置 [1,1]，值=5，target=5
     * .    5 == 5，找到目标！返回 true
     * .    0   1
     * .  +---+---+
     * .1 | 2 |[5]| ← 找到目标元素！
     * .  +---+---+
     * .<p>
     * .========================================
     * .Z字形搜索路径可视化：
     * .========================================
     * .<p>
     * .    1   4   7   11  15
     * .                 ↑   ①  (15 > 5，向左)
     * .    2   5   8   12  19
     * .             ↑   ②      (11 > 5，向左)
     * .    3   6   9   16  22
     * .         ↑   ③          (7 > 5，向左)
     * .    10  13  14  17  24
     * .     ↓   ④              (4 < 5，向下)
     * .    18  21  23  26  30
     * .        ⑤               (5 == 5，找到！)
     * .<p>
     * .搜索路径：15 → 11 → 7 → 4 → 5 （形成Z字形）
     * .<p>
     * .========================================
     * .复杂度分析：
     * .========================================
     * .<p>
     * .时间复杂度：O(m + n)
     * .- 最坏情况下，需要从右上角走到左下角
     * .- 每次移动都会排除一行或一列
     * .- 最多向左移动 n 次，向下移动 m 次
     * .- 总移动次数最多为 m + n - 1
     * .<p>
     * .空间复杂度：O(1)
     * .- 只使用了常数个额外变量（row, col）
     * .- 不需要额外的数据结构
     * .<p>
     * .========================================
     * .其他解法对比：
     * .========================================
     * .<p>
     * .1. 暴力法：O(m*n) 时间，遍历所有元素
     * .2. 逐行二分查找：O(m*log n) 时间，对每行进行二分查找
     * .3. Z字形查找（本解法）：O(m+n) 时间，最优解
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // 边界条件检查：空矩阵
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        // 获取矩阵的行数和列数
        int rows = matrix.length;    // 矩阵的行数
        int cols = matrix[0].length; // 矩阵的列数

        // 从矩阵的右上角开始搜索
        // 右上角的特性：向左递减，向下递增
        int row = 0;           // 当前行索引，从第一行开始
        int col = cols - 1;    // 当前列索引，从最后一列开始（右上角）

        // 当行索引和列索引都在有效范围内时，继续搜索
        while (row < rows && col >= 0) {
            int currentValue = matrix[row][col];

            // 情况1：找到目标值
            if (currentValue == target) {
                return true;
            }
            // 情况2：当前值大于目标值
            // 说明目标值不可能在当前列（当前列从上到下递增，当前值已经大于目标）
            // 需要向左移动，排除当前列
            else if (currentValue > target) {
                col--; // 向左移动一列
            }
            // 情况3：当前值小于目标值
            // 说明目标值不可能在当前行（当前行从左到右递增，当前值已经小于目标）
            // 需要向下移动，排除当前行
            else {
                row++; // 向下移动一行
            }
        }

        // 搜索完毕，未找到目标值
        return false;
    }

    public static void main(String[] args) {
        S76_Mid_240_搜索二维矩阵_II solution = new S76_Mid_240_搜索二维矩阵_II();

        System.out.println("=== 搜索二维矩阵 II 测试开始 ===");

        // 测试1: LeetCode示例1 - 找到目标值5
        System.out.println("\n--- 测试1: 标准矩阵查找存在的值 ---");
        testCase1(solution);

        // 测试2: LeetCode示例2 - 未找到目标值20
        System.out.println("\n--- 测试2: 标准矩阵查找不存在的值 ---");
        testCase2(solution);

        // 测试3: 单行矩阵
        System.out.println("\n--- 测试3: 单行矩阵 ---");
        testSingleRow(solution);

        // 测试4: 单列矩阵
        System.out.println("\n--- 测试4: 单列矩阵 ---");
        testSingleColumn(solution);

        // 测试5: 单元素矩阵
        System.out.println("\n--- 测试5: 单元素矩阵 ---");
        testSingleElement(solution);

        // 测试6: 目标值在左上角
        System.out.println("\n--- 测试6: 目标值在左上角 ---");
        testTopLeft(solution);

        // 测试7: 目标值在右下角
        System.out.println("\n--- 测试7: 目标值在右下角 ---");
        testBottomRight(solution);

        // 测试8: 目标值小于所有元素
        System.out.println("\n--- 测试8: 目标值小于所有元素 ---");
        testTargetTooSmall(solution);

        // 测试9: 目标值大于所有元素
        System.out.println("\n--- 测试9: 目标值大于所有元素 ---");
        testTargetTooLarge(solution);

        // 测试10: 大矩阵测试
        System.out.println("\n--- 测试10: 大矩阵测试 ---");
        testLargeMatrix(solution);

        // 测试11: 包含负数的矩阵
        System.out.println("\n--- 测试11: 包含负数的矩阵 ---");
        testNegativeNumbers(solution);

        // 测试12: 所有元素相同
        System.out.println("\n--- 测试12: 所有元素相同 ---");
        testAllSameElements(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: LeetCode示例1 - 查找存在的目标值5
     */
    private static void testCase1(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        int target = 5;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值5";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: LeetCode示例2 - 查找不存在的目标值20
     */
    private static void testCase2(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        int target = 20;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值20";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 单行矩阵
     */
    private static void testSingleRow(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {{1, 3, 5, 7, 9}};
        int target = 5;

        System.out.println("矩阵: [1, 3, 5, 7, 9]");
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值5";

        // 测试不存在的值
        target = 4;
        System.out.println("查找目标: " + target);
        result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值4";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 单列矩阵
     */
    private static void testSingleColumn(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {{1}, {3}, {5}, {7}, {9}};
        int target = 7;

        System.out.println("矩阵: [[1], [3], [5], [7], [9]]");
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值7";

        // 测试不存在的值
        target = 6;
        System.out.println("查找目标: " + target);
        result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值6";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单元素矩阵
     */
    private static void testSingleElement(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {{5}};
        int target = 5;

        System.out.println("矩阵: [[5]]");
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值5";

        target = 1;
        System.out.println("查找目标: " + target);
        result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值1";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 目标值在左上角
     */
    private static void testTopLeft(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {1, 4, 7},
                {2, 5, 8},
                {3, 6, 9}
        };
        int target = 1;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target + " (左上角)");

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到左上角的值1";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 目标值在右下角
     */
    private static void testBottomRight(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {1, 4, 7},
                {2, 5, 8},
                {3, 6, 9}
        };
        int target = 9;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target + " (右下角)");

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到右下角的值9";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 目标值小于所有元素
     */
    private static void testTargetTooSmall(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {5, 8, 11},
                {6, 9, 12},
                {7, 10, 13}
        };
        int target = 1;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target + " (小于所有元素)");

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "目标值小于所有元素，不应该找到";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 目标值大于所有元素
     */
    private static void testTargetTooLarge(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {1, 4, 7},
                {2, 5, 8},
                {3, 6, 9}
        };
        int target = 100;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target + " (大于所有元素)");

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "目标值大于所有元素，不应该找到";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 大矩阵测试
     */
    private static void testLargeMatrix(S76_Mid_240_搜索二维矩阵_II solution) {
        // 创建一个10x10的矩阵
        int[][] matrix = new int[10][10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                matrix[i][j] = i * 10 + j + 1;
            }
        }

        System.out.println("矩阵: 10x10 (值从1到100)");
        int target = 55; // 中间的值

        System.out.println("查找目标: " + target);
        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值55";

        target = 101; // 不存在的值
        System.out.println("查找目标: " + target);
        result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值101";
        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 包含负数的矩阵
     */
    private static void testNegativeNumbers(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {-5, -3, -1, 2, 4},
                {-4, -2, 0, 3, 5},
                {-3, -1, 1, 4, 6},
                {-2, 0, 2, 5, 7}
        };
        int target = -2;

        System.out.println("矩阵:");
        printMatrix(matrix);
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值-2";

        target = -6;
        System.out.println("查找目标: " + target);
        result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值-6";
        System.out.println("✓ 测试11通过");
    }

    /**
     * .测试12: 所有元素相同
     */
    private static void testAllSameElements(S76_Mid_240_搜索二维矩阵_II solution) {
        int[][] matrix = {
                {5, 5, 5},
                {5, 5, 5},
                {5, 5, 5}
        };
        int target = 5;

        System.out.println("矩阵: 所有元素都是5");
        printMatrix(matrix);
        System.out.println("查找目标: " + target);

        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: true)");
        assert result : "应该找到目标值5";

        target = 3;
        System.out.println("查找目标: " + target);
        result = solution.searchMatrix(matrix, target);
        System.out.println("searchMatrix() -> " + result + " (期望: false)");
        assert !result : "不应该找到目标值3";
        System.out.println("✓ 测试12通过");
    }

    /**
     * .辅助方法：打印矩阵
     */
    private static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.print("[");
            for (int j = 0; j < row.length; j++) {
                System.out.printf("%3d", row[j]);
                if (j < row.length - 1) {
                    System.out.print(", ");
                }
            }
            System.out.println("]");
        }
    }
}
